Storage devices are used to store various types of digital items, such as documents, images, database objects, data extents, data files, audio files, video files, etc. To ensure that valuable items are not permanently lost, it is common for items to be mirrored across multiple storage devices. For example, assume that a system includes five storage devices that are used to store five items. Rather than store each of the five items on a single one of the five disks, copies of each of the items may be stored on two different disks within the system. Because, for each item, copies are stored on two different disks, the failure of any one disk will not cause any item to be lost.
Storage devices, no matter how large and fast, have finite I/O processing capabilities. If too many read requests are issued to any particular storage device, the performance of the system suffers. Consequently, techniques have been developed to balance the load of read requests that target any particular item among the storage devices that store copies of the item. For example, if disks A and B store copies of an item X, then half of the read requests that target item X may be issued to disk A, and the other half of the read requests that target item X may be issued to disk B. To accomplish this distribution, the storage system may simply alternate read requests for item X between the two disks, or divide item X into two logical volumes, where read requests that map to one of the volumes are issued to disk A, and read requests that map to the other volume are issued to disk B.
Systems that evenly balance read requests that target a particular item between the storage devices that have copies of the item work well as long as the items are evenly spread among the storage devices in the system, each item receives approximately the same number of read requests, and no device fails. However, various circumstances may lead to situations in which items are not spread evenly and/or different items receive vastly different numbers of I/O requests.
For example, it is not uncommon for some items to become “hot spots” to which read requests are issued at a much higher frequency than other items. Depending on the nature of the data that is stored on the storage devices, such hot spots may correspond, for example, to an important just-released news story, a popular song, or hot stock prices stored in a database. Regardless of the cause of hot spots, unless the hot spots are distributed evenly among the storage devices, some storage devices may become overloaded while others are underutilized.
One way of mitigating the detrimental effect of hot spots is to move copies of items that have hot spots to storage devices that are otherwise underutilized. This may work well if hot-spots were constant and predictable, but items that may be highly accessed at one point of time may be rarely accessed at other times. Consequently, moving copies of items among storage devices to mitigate hot spots may cause more performance problems than are caused by the hot spots themselves.
Situations that skew the distribution of items among a set of storage devices are also common. For example, assume that two copies each of five items are distributed evenly among five storage devices, as shown in system 100 of FIG. 1. If the five items (A-E) are accessed at the same rate, and the read requests for each item are divided equally among the copies of the item, then the workload on each storage device (102-110) will be approximately the same. However, if one of those devices fails, all of the I/O requests that would have been handled by that failed device will have to be handled by the two devices that have copies of the items that were on the failed device. This causes those two devices to be overloaded, while the other two storage devices continue to receive the same number of read requests they received prior to the failure.
Specifically, assume that storage device 102 fails. After the failure, all of the read requests for item A will be sent to storage device 104, and all of the read requests for item E will be sent to storage device 110. The I/O load of storage devices 106 and 108 would not be affected. Assuming that all five items are being accessed at the same rate (e.g. 100 reads per second), the I/O load for each of storage devices 104 and 110 will be 50% higher (150 reads per second) than the I/O load for each of storage devices 106 and 108 (100 reads per second).
One way to reduce the workload skew that results when a storage device fails is to ensure that the items on any given storage device are mirrored, randomly or otherwise, across a large number of other storage devices. Consequently, when the storage device fails, the extra read load that will be incurred by other devices when the device fails will not be too significant for any one storage device. However, the overhead incurred by creating and managing relatively fine-granularity items that are mirrored across large numbers of storage devices reduces any benefit achieved by the improved post-failure workload distribution. In addition, spreading the mirror copies randomly over a large number of storage devices makes the system (a set of devices) more prone to loss of availability of data in the event of multiple failures.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.